package leetcode.top100;

import utils.TreeNode;

/**
 * 给定一个二叉树，它的每个结点都存放着一个整数值。
 * <p>
 * 找出路径和等于给定数值的路径总数。
 * <p>
 * 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
 * <p>
 * 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
 * <p>
 * 示例：
 * <p>
 * root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
 * <p>
 * 10
 * /  \
 * 5   -3
 * / \    \
 * 3   2   11
 * / \   \
 * 3  -2   1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/path-sum-iii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @date 2020/5/23 22:09
 */
public class Code437_PathSum3_路径总和3 {

    public int pathSum(TreeNode treeNode, int sum) {
        if (treeNode == null) return 0;
        int[] path = new int[1000];

        return process2(treeNode, sum, path, 0);
    }

    private static int process2(TreeNode root, int sum,
                                int[] path/*保存路径*/,
                                int index/*指向路径终点*/) {
        if (root == null) return 0;
        path[index] = root.val;
        int n = 0;
        int temp = 0;
        //从当前节点往父节点找路径
        //数组长度最大是logn
        for (int i = index; i >= 0; i--) {
            if ((temp += path[i]) == sum) n++;
        }
        int left = process2(root.left, sum, path, index + 1);
        int right = process2(root.right, sum, path, index + 1);
        return n + left + right;
    }

}
